package Heap;

import java.util.*;

public class _743_NetworkDelayTime {
//    public int networkDelayTime(int[][] times, int N, int K) {
//        int res = 0;
//        int[][] distances = new int[N+1][N+1];
//        for (int i = 1; i < N + 1; i++) {
//            for (int j = 1; j < N + 1; j++) {
//                if (i == j) {
//                    distances[i][j] = 0;
//                } else {
//                    distances[i][j] = 9999;
//                }
//            }
//        }
//        for (int i = 0; i < times.length; i++) {
//            for (int j = 0; j < 3; j++) {
//                distances[times[i][0]][times[i][1]] = times[i][2];
//            }
//        }
//        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
//                (info1, info2) -> info1[1] - info2[1]);
//        Map<Integer, Integer> jumps = new HashMap<>();
//        for (int i = 0; i < N; i++) {
//            heap.offer(new int[]{i + 1, distances[K][i + 1]});
//            jumps.put(i + 1, 1);
//        }
//
////        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
////            @Override
////            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
////                return o1.getValue() - o2.getValue();
////            }
////        });
//        while (!heap.isEmpty()) {
//            int[] index = heap.poll();
//            for (int j = 1; j < N + 1; j++) {
//                if (distances[K][j] > distances[K][index[0]] + distances[index[0]][j]) {
//                    jumps.put(j, jumps.get(j) + 1);
//                    distances[K][j] = Math.min(distances[K][j], distances[K][index[0]] + distances[index[0]][j]);
//                }
//            }
//        }
//        for (int i = 1; i < N+1; i++) {
//            if (distances[K][i] == 9999) {
//                return -1;
//            }
//
//        }
//        for (Map.Entry<Integer,Integer> e:jumps.entrySet()) {
//            res = Math.max(res, e.getValue());
//        }
//        return res;
//    }
public int networkDelayTime(int[][] times, int N, int K) {
    Map<Integer, List<int[]>> graph = new HashMap();
    for (int[] edge: times) {
        if (!graph.containsKey(edge[0]))
            graph.put(edge[0], new ArrayList<int[]>());
        graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
            (info1, info2) -> info1[0] - info2[0]);
    heap.offer(new int[]{0, K});

    Map<Integer, Integer> dist = new HashMap();

    while (!heap.isEmpty()) {
        int[] info = heap.poll();
        int d = info[0], node = info[1];
        if (dist.containsKey(node)) continue;
        dist.put(node, d);
        if (graph.containsKey(node))
            for (int[] edge: graph.get(node)) {
                int nei = edge[0], d2 = edge[1];
                if (!dist.containsKey(nei))
                    heap.offer(new int[]{d+d2, nei});
            }
    }

    if (dist.size() != N) return -1;
    int ans = 0;
    for (int cand: dist.values())
        ans = Math.max(ans, cand);
    return ans;
}
}
